//翻转对
//测试链接 https://leetcode.cn/problems/reverse-pairs/
public class ReversePairsTwo {
    int[] help;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        help = new int[n];

        return mergeSort(nums, 0, n-1);
    }

    public int mergeSort(int[] nums,  int left, int right){
        if(left >= right) return 0;
        int mid = left + (right - left) / 2;

        int ret = 0;
        ret += mergeSort(nums,left,mid);     //左部分的翻转对个数
        ret += mergeSort(nums,mid+1, right); //右部分的翻转对个数

        int cur1 = left, cur2 = mid+1;
        while(cur1 <= mid){ //降序
            //寻找到nums[cur1] > 2*nunms[cur2] 的位置
            while(cur2 <= right && nums[cur1]/2.0 <= nums[cur2]) cur2++;
            if(cur2 > right) break;

            ret += right - cur2 + 1;
            cur1++;
        }

        //排序
        cur1 = left; cur2 = mid+1;
        int i = left;
        while(cur1 <= mid && cur2 <= right){
            if(nums[cur1] >= nums[cur2]) help[i++] = nums[cur1++];
            else help[i++] = nums[cur2++];
        }
        //处理剩下的
        while(cur1 <= mid) help[i++] = nums[cur1++];
        while(cur2 <= right) help[i++] = nums[cur2++];
        //合并到原数组
        for(int j = left ; j <= right; j++){
            nums[j] = help[j];
        }

        return ret;
    }
}
